
//荷兰国旗问题：
int* Netherlands(int arr[], int l,  int r)
{
	if (l > r) {
		return NULL;
	}
	if (l == r) {
		return NULL;
	}
	int less = l - 1;
	int more = r;
	int index = l;
	while (index < more) {
		if (arr[index] == arr[r]) {
			index++;
		}
		else if (arr[index] < arr[r]) {
			swap(arr[index++], arr[++less]);
		}
		else {
			swap(arr[index], arr[--more]);
		}
	}
	swap(arr[more], arr[r]);
	int* ret = new int[2];
	ret[0] = less + 1, ret[1] = more;
	return ret;
}
//随机快排递归版
void process_qsort(int* arr, int l, int r)
{
	if (l >= r) return;
	
	int* tmp = Netherlands(arr, l, r);
	process_qsort(arr, l, tmp[0] - 1);  //递归左区间
	process_qsort(arr, tmp[1] + 1, r);  //递归右区间
}

//随机快排非递归版
void qsortNoR(int arr[], int l,int r) 
{
	int* equalArea = Netherlands(arr, l, r);
	stack<pair<int,int>> st;
	int el = equalArea[0];
	int er = equalArea[1];
	st.push(make_pair(0, el - 1));
	st.push(make_pair(er + 1, r));

	while (!st.empty()) {
		auto op = st.top();
		st.pop();
		if (op.first < op.second) {
			equalArea = Netherlands(arr, op.first, op.second);
			el = equalArea[0];
			er = equalArea[1];
			st.push(make_pair(op.first, el - 1));
			st.push(make_pair(er + 1, op.second));
		}
	}
} 
